package fig;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 王圆豪
 * Date: 2024-11-25
 * Time: 13:04
 */
import java.util.*;

public class GraphAdjList {
    private LinkedList<Integer>[] adjList;
    private int vertices;

    public GraphAdjList(int vertices) {
        this.vertices = vertices;
        adjList = new LinkedList[vertices];
        for (int i = 0; i < vertices; i++) {
            adjList[i] = new LinkedList<>();
        }
    }

    // 添加边
    public void addEdge(int start, int end) {
        adjList[start].add(end);
        adjList[end].add(start);
    }

    // 打印图
    public void printGraph() {
        System.out.println("邻接表表示的图：");
        for (int i = 0; i < vertices; i++) {
            System.out.print((char)('A' + i) + ": ");
            for (Integer neighbor : adjList[i]) {
                System.out.print((char)('A' + neighbor) + " ");
            }
            System.out.println();
        }
    }

    // 深度优先搜索
    public void dfs(int start) {
        boolean[] visited = new boolean[vertices];
        System.out.print("深度优先搜索遍历：");
        dfsUtil(start, visited);
        System.out.println();
    }

    private void dfsUtil(int vertex, boolean[] visited) {
        visited[vertex] = true;
        System.out.print((char)('A' + vertex) + " ");
        for (Integer neighbor : adjList[vertex]) {
            if (!visited[neighbor]) {
                dfsUtil(neighbor, visited);
            }
        }
    }

    // 广度优先搜索
    public void bfs(int start) {
        boolean[] visited = new boolean[vertices];
        Queue<Integer> queue = new LinkedList<>();
        visited[start] = true;
        queue.add(start);

        System.out.print("广度优先搜索遍历：");
        while (!queue.isEmpty()) {
            int vertex = queue.poll();
            System.out.print((char)('A' + vertex) + " ");
            for (Integer neighbor : adjList[vertex]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.add(neighbor);
                }
            }
        }
        System.out.println();
    }

    public static void main(String[] args) {
        GraphAdjList graph = new GraphAdjList(5); // 创建一个有5个节点的图
        graph.addEdge(0, 1); // A - B
        graph.addEdge(0, 2); // A - C
        graph.addEdge(1, 3); // B - D
        graph.addEdge(2, 3); // C - D
        graph.addEdge(3, 4); // D - E

        graph.printGraph();
        graph.dfs(0); // 从节点A开始深度优先搜索
        graph.bfs(0); // 从节点A开始广度优先搜索
    }
}